Depends on this year's snowpack and much of MT and WY's comes in April/early May. As Longhorn said, you can look at statistics as to when Yellowstone is typically open, but you'll just have to check with YNP personnel to be sure. One consistent fact is that the Beartooth Highway, US 212 from Red Lodge, MT into YNP via the Northeast Entrance, is rarely open before Memorial Day. The Beartooth Highway is considered by many as a must-see. Likely some or most of the higher elevation disbursed campsites in the NFs surrounding YNP will be inaccessible before mid- to late May, too.
If you're looking at off highway trails and higher passes off of the beaten path, an average snowpack will likely have them closed through May, too.
Trout fishing can be difficult to impossible in May due to high waters from the runoff.
In the Dakotas, SD can be somewhat easier to get around, within the Black Hills, when wet during the Spring. Outside of the Black Hills, much of western SD and practically all of western ND and eastmost MT is badlands type geology developed from volcanic ash deposits. The ash weathers to a bentonite clay often referred to as gumbo when it gets wet. It is a highly absorbent clay and becomes slicker than goose poop when wet. It'll pack up the treads of all but the most exactly designed AT tires. In and around the Teddy Roosevelt NP and the units of National Grasslands in its vicinity, the term "impassible when wet" really means something. Besides, the best way to incur the ire of ranchers out there is to drive on the clay roads when they're wet. They've got to deal with the resulting ruts until the next semi-annual grader pass. The good news is that a full day, day and a half of sun and a good breeze dries the clay roads out back to the consistency of concrete.
Coming from TX to the Dakotas, I'd be sure to snag a piece of the Nebraska Sandhills along the way up or back. Plan a half-day at Seneca, NE for a 2-3 hour float of the Middle Loup River in a stock tank. Glidden's Motel and Canoe Rentals has the franchise, and a float down the Middle Loup in a 10' diameter livestock watering tank (known as a "tanking" trip), is a great way to see the Sandhills. About 30 miles SE along Nebraska Route 2 is the Halsey unit of the Nebraska NF. Their campground is very nice, is on the same river, and has fine modern bathhouses/showers.
Foy