Identifying the location of the dermal epidermal junction (DEJ) in skin images is essential in several clinical applications of dermatology such as epidermal thickness determination in healthy versus unhealthy skins, such as basal cell carcinoma. Optical coherence tomography (OCT) facilitates the visual detection of DEJ in vivo. However, due to the granular texture of speckle and a low contrast between dermis and epidermis, a skin border detection method is required for DEJ localization. Current DEJ algorithms work well for skins with a visible differentiable epidermal layer but not for the skins of different body sites. In this paper, we present a semi-automated DEJ localization algorithm based on graph theory for OCT images of skin. The proposed algorithm is performed in an interactive framework by a graphical representation of an attenuation coefficient map through a uniform-cost search method. For border thinning, a fuzzy-based nonlinear smoothing technique is used. For evaluation, the DEJ detection method is used by several experts, and the results are compared with manual segmentation. The mean thickness error between the proposed algorithm and the experts' opinion in the Bland-Altman plot is computed as 14 μm; this is comparable to the resolution of the OCT. The results suggest that the proposed image processing method successfully detects DEJ.