Even though soft tissues are of primary interest to radiologists, they are represented using only 12.5% of the total number of gray levels in a typical DICOM format of a Computed Tomography (CT) scan. This poor distribution of gray levels reduces the overall contrast and the texture differences between individual organs, and poses a serious visualization problem since radiologists need clear visual representations of organs to produce proper diagnoses. In order to enhance the contrast within the soft tissues, the gray levels can be redistributed both linearly and nonlinearly using the gray level frequencies of the original CT scan. We propose a new nonlinear approach for contrast enhancement of soft tissues in CT images using both clipped binning and nonlinear binning based on a k-means clustering algorithm. The optimal number of bins, in particular the number of gray-levels, is chosen automatically using entropy and average distance between the histogram of the original gray-level distribution and the contrast enhancement function's curve. The contrast enhancement results were obtained and evaluated using 141 CT images of the chest and abdomen from two normal CT studies.