The short version: the Abu Dhabi government went to Colt in 1984 and asked for a carbine version of the then-new M16A2. They wanted all the same features, including the ability to mount the M203, but with a shorter barrel. Thus was born what we now call the M4 Carbine, though then they were often called "Abu Dhabi Carbines."
They were first shopped around to the US military in '86, and one of the generals wanted to buy them and replace most handguns with them (similar to the concept for the M1 Carbine in WWII). That, of course, didn't happen, but many SpecOps units bought them to replace their worn-out XM177s. The M4 Carbine designation was given at that time. By the late 80s, the Army was buying M4s in small numbers for Airborne units (82nd and 101st) and Rangers for use on specific missions.
Desert Shield/Storm was the place where the M4 got noticed, because many commanding officers saw them there for the first time and wanted some for their units. They were definitely in use in Somialia in '93 (by Delta and some of the Rangers who fast-roped in), and you know the story from there.
-Troy