The oldest probable uniramian known to date is Cambropodus, from the Middle Cambrian of Utah; unfortunately, the only fossil is incomplete and not well preserved. Cambropodus was apparently a marine form, but the great majority of living uniramians are terrestrial.
Very little is known about the history of the Uniramia until the Silurian, when the first myriapods (centipedes, millipedes, and their kin) appeared. In the middle Devonian the first collembolans (springtails) made their appearance, and by the Pennsylvanian, or late Carboniferous, winged insects were present, including the first mayflies and cockroaches. The Permian saw the appearance of stoneflies, true bugs, beetles, and caddisflies, among other groups. A mass extinction event 245 million years ago, the Permo-Triassic event, not only wiped out much of the marine biota, it also affected the land severely; a number of insect groups went extinct at the time. The fossil pictured below is a millipede from the Pennsylvanian-age Mazon Creek fauna of Illinois, preserved in a nodule of siderite (iron carbonate) that formed around it before it could decay.
The oldest true flies are Triassic in age; butterflies appear in the Jurassic; and by the end of the Cretaceous, almost all the familiar uniramian groups had appeared. Insects and other uniramians, as far as we can tell, were completely unaffected by the extinction event at the end of the Cretaceous, which wiped out the last of the dinosaurs. Insects continued to diversify in the Cenozoic, leaving fossil traces behind. This fly, for instance, is from the Oligocene-age Florissant Shale of Colorado (about 35 million years old).
The Fossils of New Jersey page includes a nice photo of a Cretaceous insect in amber.