Phytosanitary measures are a major barrier to trade in papaya. We assessed the infestation of tephritid fruit flies on different stages of maturity of papaya, to determine its non-host stage of maturity, for market access. Papaya fruits were collected from Kilifi and Embu counties, Kenya from March 2013 to December 2014, to assess the level of infestation by fruit flies according to the degree of fruit ripening. In all locations, no fruit fly infestation was recorded on papaya when fruits were at the 0, 25 and 50% yellow fruit ripening stage. Bactrocera dorsalis (Hendel) was, however, observed attacking fruits when papaya fruits were at 75 and 100% all yellow (fully ripe fruit ripening stage) with infestations of 0.19−0.51 B. dorsalis/kg fruit and 0.24−1.24 B. dorsalis/kg fruit, respectively, in all locations. Field cage exposure of B. dorsalis to fruits of five papaya cultivars—‘Papino’, ‘Neo Essence’, ‘Sunrise Solo’, ‘Tainung No. 1’ and ‘Tainung No. 2’ in Manica Province, Mozambique—showed that B. dorsalis did not infest fruits at 0, 25 and 50% yellow ripening stages at the densities of 50 and 100 flies per cage. However, at 75% yellow ripening stage, up to 13.1 pupae/kg of fruits was recorded at a density of 150 flies per cage in Tainung No. 1, and infestation ranged from 4.5 to 136 pupae/kg fruits at 100% yellow ripening stage across all the cultivars and infestation densities. Laboratory evaluation of volatiles emanating from freshly crushed papaya pulp of four cultivars: ‘Sunrise Solo’, ‘Red Lady’, ‘Papayi’ and ‘Apoyo’ on egg viability of B. dorsalis showed that at 0, 25 and 50% yellow, egg hatchability was inhibited, suggesting that semiochemical compounds present in green tissues of papaya prevent egg development, although this effect was variable across the four cultivars and ripening stages. Export papaya is harvested at less than 40% yellow ripening stage. Our results, therefore, suggest that quarantine treatment for fruits at this ripening stage is inconsequential, as B. dorsalis does not infest papaya fruits at this stage; thus, authorities should permit entry of these papaya cultivars of less than 40% yellow ripening stage to quarantine-sensitive markets.