Not one of the 50 states has always voted for the Democrat or Republican — even if we only look at races for the presidency.
At any given time, some states are very likely to vote one way or another.
Right now (2018), for instance, NY and CA are very likely to vote for Democrats for President and TX is very likely to vote Republican.
However, if we go back to 1968 TX voted for Humphrey over Nixon. In that same election, VT (now a liberal Democratic stronghold) voted for Nixon over Humphrey.
In the LBJ landslide of 1964, Johnson got every state outside the deep south except for Goldwater’s native state of Arizona. E.g. Johnson carried UT, WY and OK, now three of the most Republican states. (Goldwater carried Arizona, Louisiana, Mississippi, Alabama, Georgia and South Carolina).
Regionally, the biggest shift was in the states of the deep south. These went from solidly Democratic to solidly Republican and the shift was fairly recent. In 1952, they went solidly for Stevenson, the Democrat (and Stevenson won no states outside the deep south except for West Virginia and Kentucky). In 1956, Stevenson again won all the deep southern states but added Missouri while Kentucky and Virginia went to Eisenhower. In 1956, Eisenhower won the popular vote 57–42. Eisenhower’s biggest proportions were in Vermont, Maine, New Hampshire, Nebraska and Kansas. Stevenson’s were in Georgia, Mississippi, Alabama and Arkansas. 1960 was a very odd year; not only was the race close, but two southern states had a lot of “unpledged electors”.
Nevertheless, Kennedy did quite well in the deep south. Then came Lyndon Johnson. Already in 1964, the south was solidly against Johnson. Goldwater’s best state was Mississippi. So, in 1956, Mississippi gave 58% to the Democrat, while 8 years later it gave 87% to the Republican. The contrast is even starker if we compare it to the national vote. In 1956, Mississippi gave the Democrat 16% more than he got nationally. In 1964, it gave the Democrat 49% less.
Another big shift, in the opposite direction, was in New England. In 1936 Roosevelt lost only two states: Maine and Vermont. His worst states were Maine, Vermont, Massachusetts and Rhode Island. New England remained at least as Republican as the rest of the country for several elections. In 1948, Thomas Dewey won most of New England. In 1952, Eisenhower won all of it and his best state was Vermont. But, as in the south, everything changed in 1964. New England was solidly for Johnson over Goldwater, and Rhode Island, Massachusetts and Maine were among his best states.
Have any states been consistent?
Hawaii has voted pretty consistently for Democrats for president, but it went for Nixon over McGovern in 1972 (and by more than the national average) and for Reagan in 1984.
Trump’s best states in 2016 were Wyoming, West Virginia and Oklahoma. The last time West Virginia voted for a Democrat for president was 1976 when they supported Jimmy Carter; they also supported Humphrey in 1968. All three states voted for Johnson in 1964.