Barring anything theater-based (like Classical, Opera and Broadway), can anyone tell me which was the first true "concept album"? Pink Floyd's "Dark Side Of The Moon" held a concept throughout it, and that was released in 1973. I have to believe something came before that.
If we define a concept album as one whereby the tracks are linked in some way, there are some early examples of albums that are thematically linked - for example, Sinatra's Come Fly with Me (1958), all about travel. There are arguably many examples earlier than this, but with some it's hard to draw the line between a theme that is an intentional concept, and one that is a natural product of the writer's circumstance or inspiration. Woody Guthrie's Dust Bowl Ballads (1940) is one that might come down on one side or the other, depending on your judgement.
The real rise in popularity of the Rock concept album seems to have been in the mid to late 60s. The Beach Boys' Pet Sounds (1966) is often considered a concept album due to common threads in production and themes between many of the songs. The Beatles' Sgt. Pepper's Lonely Hearts Club Band (1967) is based around the more oblique concept of the eponymous band being the actual act featured in the album, while The Who Sell Out (1967) is produced to sound like a pirate radio broadcast.
One of the first successful albums to feature a set of songs unified by a story is S.F. Sorrow (1968) by the Pretty Things.
So, as with many things, It depends on your definition, but whichever you choose, the mid-late 60s seems to be the real taking-off period for successful concept albums.