Veteran received generally mixed to positive reviews from music critics. AllMusic editor Andy Kellman praised the production and lyrical qualities for being more hi-standard compared to Houston's previous efforts and for the maturity in his vocal delivery, saying that "he works the more romantic sentiments with enough conviction to indicate that he has more life experiences from which to draw." Joshua Alston of Vibe saw Houston's vocal work similar to that of Sam Cooke, saying that he "sounds sexier when he isn't working so damn hard at it. If only he had a clue."
Adam Pearthree of Okayplayer commended the mature approach the album takes with its songs but found it forgettable, along with Houston's identity crisis in his vocal performance, concluding that, "With stronger song selection [Marques] Houston could still come up with the adult oriented album he wants, but as of now, Veteran simply falls short." Mike Joseph of PopMatters also found the production and songwriting adequate at best but felt it was too reminiscent of other established R&B artists, saying that "[T]he moments you notice on Veteran are the ones that remind you of other artists. Now in his mid-twenties, it’s hard to say whether Houston will ever develop the singular personality that will elevate his career to the next level of hitmaker status."
In the United States, Veteran debuted and peaked at number 5 on the US Billboard200, and number 1 on Billboard's Top R&B/Hip-Hop Albums. This marked Houston's first number one solo album as well as his highest-charting album yet. Veteran sold almost 70,000 units in its first week.