Yield strength of highly dislocated metals is known to be directly proportional to the square root of dislocation density (ρ), so called Bailey-Hirsch relationship. In general, the microstructure of heavily cold worked iron is characterized by cellar tangled dislocations. On the other hand, the dislocation substructure of martensite is characterized by randomly distributed dislocations although it has almost same or higher dislocation density in comparison with heavily cold worked iron. In this paper, yielding behavior of ultra low carbon martensite (Fe-18%Ni alloy) was discussed in connection with microstructural change during cold working. Originally, the elastic proportional limit and 0.2% proof stress is low in as-quenched martensite in spite of its high dislocation density. Small amount of cold rolling results in the decrease of dislocation density from 6.8x1015/m-2 to 3.4x1015/m-2 but both the elastic proportional limit and 0.2% proof stress are markedly increased by contraries. 0.2% proof stress of cold-rolled martensite could be plotted on the extended line of the Bailey-Hirsch equation obtained in cold-rolled iron. It was also confirmed that small amount of cold rolling causes a clear microstructural change from randomly distributed dislocations to cellar tangled dislocations. Martensite contains two types of dislocations; statistically stored dislocation (SS-dislocation) and geometrically necessary dislocation (GN-dislocation). In the early deformation stage, SS-dislocations easily disappear through the dislocation interaction and movement to grain boundaries or surface. This process produces a plastic strain and lowers the elastic proportional limit and 0.2% proof stress in the ultra low carbon martensite.