โอกูโบะ โทชิมิจิ เกิดที่เมืองคาโงชิมะ แคว้นซัตสึมะ (ปัจจุบันคือจังหวัดคาโงชิมะ) โดยเป็นบุตรชายคนโตจากทั้งหมด 5 คน ของโอกูโบะ จูเอมง ซามูไรระดับล่างผู้เป็นข้ารับใช้ของชิมัตสึ นาริอากิระ ไดเมืยวแห่งแคว้นซัตสึมะ เขาได้รับการศึกษาในสำนักศึกษาของท้องถิ่นแห่งเดียวกันร่วมกับไซโง ทากาโมริ ซึ่งมีอายุมากกว่าเขาเพียง 3 ปี ในปี ค.ศ. 1846 โอกูโบะได้รับตำแหน่งเป็นผู้ช่วยอาลักษณ์ประจำแคว้นซัตสึมะ