Malaking bahagi ng kasalukuyang nasasakupan ng Misamis Oriental ay bahagi ng kinakatawan ng dating lalawigan ng Misamis (1907–1931). Hindi kabilang dito ang mga teritoryo na dinugtong noong 1921 mula sa Bukidnon (na kinakatawan ng Departamento ng Mindanao at Sulu): Napaliran (dinugtong sa Balingasag noong 1921), Claveria (naging munisipalidad noong 1950), Lourdez (ipinamahagi sa pagitan ng Alubijid, El Salvador, Initao, Manticao at Opol noong 1955) at Lumbia (ipinamahagi sa pagitan ng Cagayan de Oro at Opol noong 1954).
Sa bisa ng Batas Blg. 3537 na naaprubahan noong Nobyembre 2, 1929, hinati ang noo'y lalawigan ng Misamis sa dalawa, Misamis Occidental at Misamis Oriental, at binigyan ng tig-iisang distrito. Nagsimulang maghalal ng kinatawan ang solong distrito ng Misamis Oriental noong eleksyon 1931.
Kahit naging lungsod na ang Cagayan de Oro at Gingoog, nanatili silang kinakatawan ng lalawigan sa pamamagitan ng mga Batas Pambansa Blg. 521 (1950) at 2688 (1960).
Sa bisa ng Batas Pambansa Blg. 4669 na naipasa noong Hunyo 18, 1966, hiniwalay ang sub-province ng Camiguin upang maging ganap na lalawigan. Patuloy na nirepresentahan ng lalawigan ang Camiguin hanggang 1969.
Bahagi ito ng kinakatawan ng Rehiyon X sa Pansamantalang Batasang Pambansa, mula 1978 hanggang 1984. Mula 1984 hanggang 1986, nagpadala ng dalawang assemblymen at-large ang lalawigan sa Regular Batasang Pambansa. Ang Lungsod ng Cagayan de Oro ay nabigyan ng sariling distrito sa parehong taon.
Sa ilalim ng bagong Konstitusyon, nahati ang lalawigan sa dalawang distritong pambatas noong 1987.