In a life time, a person visits several hospitals to undergo medical examination for various health issues. When new health issues occur, a record of recent medical reports is necessary for diagnosis. Therefore it is crucial to exchange patient’s diagnostic information between the hospitals securely. To transmit such information securely in deceptive environment the effective way is encrypting and hiding it over patient digital photographic image and medical image. Among the various hiding techniques the most widely used technique for medical images is the Least Significant Bit (LSB) substitution technique. Many LSB substitution techniques were developed to enhance both security and image quality of stego-medical images. However, existing approaches were failed to maintain the quality of original images. To overcome this problem we proposed an Adaptive Row-Column (ARC) approach for LSB substitution technique that minimize mean square error (MSE) values and maximize the Peak Signal to Noise Ratio (PSNR) to get both enhanced security and image quality. To further enhance the security and image quality of stego-medical images ARC algorithm is extended to embed both original and inverted cipher text (ARC-OI).