In this paper, we establish a structure theorem of naturally ordered rpp semigroups with max-idempotents. Results on naturally ordered semigroups with max-idempotents in the literature are extended and amplified. Some previous results obtained by Blyth, McFadden, Guo and Xie on regular and abundant ordered semigroups are extended to ordered rpp semigroups.