Methods, apparatus, systems and articles of manufacture to perform region formation for usage by a dynamic binary translation are disclosed. An example apparatus includes an initial region former to form an initial region starting at a first block of hot code of a control flow graph. The initial region former also adds blocks of hot code lying on a first hottest path of the control flow graph. A region extender extends the initial region to form an extended region including the initial region. The extended region begins at a hottest exit of the initial region and includes blocks of hot code lying on a second hottest path until one of a threshold path length has been satisfied or a back edge of the control flow graph is added to the extended region. A region pruner prunes the remove all loop nests except a selected loop nest which forms a final region.