En route to a show in his third state in as many days, J. Cole is still caught up in the whirlwind surrounding the release of his much-anticipated debut album for Jay-Z's Roc Nation label. After celebrating with a party in his hometown of Fayetteville the night before, the up-and-coming hip-hop star is squeezing in interviews whenever he can spare a minute. Pulling up to a Florida venue with fans buzzing in anticipation, the 26-year-old jokes about the "cheap-ass lotion" someone handed him and admits he's finally been able to relax a little.

"I'm really just relieved, like my mind is on ease, like I'm already thinking of new raps and new songs," he says via phone. "I got new energy, new life, and there's no pressure — like all the pressure is gone."

Releasing that pressure is Cole World: The Sideline Story, which is defying Roc Nation's modest expectations and even Cole's own ambitious goals. This week the album sits at No. 1 on both iTunes and the Billboard 200, and it sold 217,000 copies in its first week, giving Cole the highest-charting hip-hop debut of the year. By the time he brings his Cole World tour to the Fillmore on Thursday, Oct. 13, he'll be a bona-fide superstar.

Cole wasn't the only Carolina artist to drop new music late last month. Albums from Raleigh's Phonte and 9th Wonder, both of Little Brother fame, were getting national attention on the same day, although Cole was the clear leader. When asked what it feels like to be the flag bearer for North Carolina hip-hop, he seems genuinely blown away.

"It's crazy when you put it like that," Cole says. "These are the things I never really thought about — like I always represented and talked about it, but I never actually thought the day would come when I was successful with album sales and in terms of, like, critics, critically acclaimed or whatever. And the fact that it's an all-Carolina movement, that makes it that much better."

Also riding the wave of Cole's success is his hometown. The release of Cole World is as much a win for Fayetteville as it is for the artist. After all, that city is known more for creating soldiers than rock stars. "We're not L.A. We're not even Charlotte. We're not even Raleigh," Cole says. "So, the fact that I'm going so hard makes everybody back home want to go hard for me. People were ecstatic and happy, because I'm representing in every project I do, every song, so many shout-outs." Like the one in "School Daze," from his 2007 mixtape The Come Up: "Take y'all back to them school days, yeah. Fayette-Nam, what up, man?"

Cole has never been ashamed of growing up in the town people call "Fayette-Nam" for its large military presence, and he's entirely convincing when he says he enjoyed every minute of his childhood there. "That was some of the best times of my life," he says. "I always say when I die, I want to come right back and just do it one more time. I wouldn't have chose to be anywhere else, because I got so many great memories and friends and, you know, stories for years."

Storytelling is something that attracted Jermaine Lamarr Cole early on. He was born in Frankfurt, Germany, in 1985; his father was black and mother white. When he was 8 months old, the military family relocated to Fayetteville, where Cole's parents eventually split up. He was raised by his mother and stepfather, and the music in their household was eclectic, to say the least. His mom listened to the folk and rock of acts like Peter, Paul & Mary and Eric Clapton, while his stepfather brought home records by 2Pac, Ice Cube and Dr. Dre. "The whole time there was this weird mixture of music going on," he once told the UK-based online magazine Blues & Soul. "If I was riding with my mom, she'd be listening to the classic rock stations, while if I was riding with my dad, he'd be listening to the Above the Rim soundtrack."

Cole began rapping at 12, and by the time he reached Terry Sanford High School in the late '90s, he was posting songs to the Internet under the name Therapist. While Therapist was becoming the latest in a long list of New South rappers online, in the world of Fayetteville, Cole was still the kid who worked at the skating rink and played high-school basketball. He was theirs.

But J. Cole had a dream. "Everybody used to talk about they was gonna be in the NBA. I felt like I really believed it," he confides. "Whenever I was thinking about it, I really believed it."

To get out of Fayetteville, you have to possess a level of determination most people don't have. Cole had determination to spare. After he graduated high school in 2003, an academic scholarship drove him to New York City, where he didn't know a soul. He attended St. John's University, studying communications and business, and graduated magna cum laude in 2007.

Plenty of people relocate to New York from the South in search of a dream. Few pester America's hippest CEO into signing them to a big label deal. Cole did. He nudged Jay-Z until the rap megastar finally bit. Cole ended up being the first artist on Roc Nation, the label Jay-Z formed in 2008 when he partnered with the live-events company Live Nation. That was just three years ago, and Cole's still trying to figure it all out. "I don't know what it was," he says. "I guess it was my personality and the things I wanted. I always had big dreams."

Cole gives much of the credit to his manager, Mark Pitts. He says Pitts was the only person who believed in him all along: "He really called it. He said, 'You're gonna shock a lot of people.'"

Jay-Z gave the talented rapper and producer plenty of time and creative control to piece together Cole World and stood to lose as much as anyone if the album didn't pan out. "I'm only into artists," Jay-Z told New York radio personality Angie Martinez of the patience he had with Cole's slow recording process. "I'm not into people that can only make hit records. I want to build artists and I want them to be here for, you know, 20 years."

Cole would bring songs to Jay-Z to get his input and feedback. While pressure came from the label to work with big-name producers, Cole was determined to craft the album on his own. "I know it was certain times where they were looking at me like, 'Ah man, why don't you go see Timbaland or something?' or 'You sure you want to do this on your own?'" Cole says. "They believe in you, of course, but at the end of the day, no one really knows."

Praise wasn't so effusive while making the record, and Cole admits he was learning on the job. But he shunned the temptation to put out an album littered with outside production. As he'd done on his own mixtapes — The Come Up, 2009's The Warm Up and last year's Friday Night Lights — Cole painstakingly crafted things his own way. "It was hard, man. You have to understand that I didn't have any credentials. Of course, at the end of the day, I'm blessed that they gave me — especially Jay-Z gave me — that space and that freedom to do it."

Those mixtapes had created quite the buzz, though, so Jay-Z wasn't banking on a totally unknown quantity. "They're a record label. They're looking for something they could sell," Cole says. "I wasn't necessarily bringing all that every day, but you could not deny the movement that was happening with these fans."

These fans, as Cole puts it, are way more than just the small pockets in North Carolina and New York. Cole has become an international entity, spurred by successful appearances on tracks with monster-selling artists like Jay-Z and B.o.B., and opening slots with Rihanna.

To outsiders, what North Carolina offers hip-hop is honest, Southern charm set to simple soul samples, like the Supremes bit Cole used in "World Is Empty," one of the stand-out tracks on The Warm Up. But to grow up in the Carolinas is to know that age and geography determine the subtleties of one's hip-hop influences. It all depends on which interstate corridor is closest to your town, as well as the era in which you grew up there. For example, Charlotteans are nearer to I-85 and I-77. That means music fans here who are in their mid-20s more likely take their cues from Atlanta and Memphis: OutKast, Pastor Troy and Three 6 Mafia rather than Nas or Jay-Z. It's an entirely different thing for kids who grew up in the eastern part of the state, nearer to I-95, the famous New York-to-Miami route.

"Oh yeah, y'all were Three 6 Mafia'd out," Cole jokes about Charlotte hip-hop fans, pointing out that he was inspired more by the heavier New York influences. Not that Cole wasn't also inspired by some Southern hip-hop, as well as whatever music the military families were bringing in from other parts of the country and world. "Fayetteville is a mixture," he says. "Fayetteville always had a crazy balance, and that's what was dope for me."

Regardless of the ingredients that form Cole's creative scope, he's undeniably a product of the South. He could tackle the same things Mississippi's Big K.R.I.T., New Orleans' Lil Wayne or Atlanta's T.I. rap about, but Cole has something they don't have: He was born here, moved to New York knowing no one, completed a four-year degree and waited outside Jay-Z's studio in the rain hoping to hand his idol a CD. Cole has played the game differently, and he doesn't fit snuggly under the typical Southern umbrella. He says this mix of experiences is his advantage. It means he can rap about anything from a coming-of-age Southern drama to being a fish out of water in Manhattan to being a college student trying to hustle a rap deal.

In "School Daze," from The Come Up, Cole relates the everykid dream that for him has become a reality: "Living life in the fast lane, but ain't passing. They dreaming, tryin' to be the next Jay-Z and Damon Dashes. I ain't even open my book and it's time to change classes." He ups the ante on the same disc in "Carolina on My Mind," rapping, "Fuck school, I'm finna sign a deal!"

Things have changed on the new disc. In "Can't Get Enough," Cole World's second single, he's already well into the game. Over a sample from a Guinean folk song, he raps, "Hey Globetrotter, Cole hotter, either way, out in London town hoes holla, 'cause they love my sound, and I got love for the underground ..."

Two days after Cole World's release, the rapper may be saying goodbye to the underground. After all, his life is now at warp speed. "Today might be the first time I've, like, sat down," he tells me. "I hadn't been on the Internet in days, so I haven't been able to keep up with press. I still got shows. I'm still on tour."