Giving up the innovative, we-can-change-the-world culture of Google is hardly an easy decision for any executive who works there. But for Sukhinder Singh Cassidy, who announced this morning that she’s leaving Google to rejoin the world of start-ups, the decision was a natural.

“My father drummed into me that I should work for myself,” says Singh Cassidy, 39, who is Google’s president for Asia-Pacific & Latin American operations until she moves to Accel Partners, the Silicon Valley venture capital firm, as CEO-in-Residence next week. “My father always told me, ‘You want to control your destiny.'”

In a company of innovators and iconoclasts, Singh Cassidy has long been one of Google’s most adventurous and global-minded executives. Born in Tanzania and raised by doctor parents–her late father was from Uganda and her mother, still a practicing gynecologist, is from India–Singh Cassidy grew up in Canada and has spent her adult life refusing to be pigeon-holed or tied down. After college at the University of Western Ontario, she took the foreign service exam and the LSATs, thinking of going to law school or maybe medical school. She took an altogether different route, joining Merrill Lynch and working in investment banking in New York and London for two years.

“I’ve always been entrepreneurial at heart,” she says. So she moved into tech via stints at Amazon.com , OpenTV and BSkyB, the News Corp.-owned British pay-TV provider. In 1999, she co-founded Yodlee, a financial-services Internet company, and headed business development there until moving to Google in 2003.

Singh Cassidy stayed at Google longer than anywhere else. Starting as the first general manager for Google Local and Maps, she took over the company’s sales organizations in Asia and Latin American when they had just 17 employees. Now it has several thousand employees in 18 offices covering 103 countries.

Why leave now? Six years is a lifetime for Singh Cassidy and she misses that entrepreneurial world. Plenty of opportunities to run a start-up have come her way over the years, but she decided to join Accel because the VC firm–the same one that backed Yodlee a decade ago–will provide “a vantage point to make wise choices,” she says. “In the next six to nine months, I’ll see a lot of companies.”

And while Accel, like its Silicon Valley rivals, has seen investment values plunge during the recession, the firm has been on a roll in terms of raising money–$1 billion for two new funds that closed to investors this past December. Singh Cassidy is drawn to “Accel’s momentum,” she says, and also to its focus on consumer Internet companies. Accel’s current investments include Facebook, Glam Media and AdMob.

Although Singh Cassidy, like many of Silicon Valley’s star women, is a stretched mom of two (a daughter, two years old , and a stepson, nine), she was not, she says, driven to change jobs by a need for flexibility–which was the subject of my post on Postcards yesterday. “For me, it’s more about what my father said: Control your destiny.”

Besides that wisdom from her late father, what’s the best advice she’s received? “When you feel it in your gut, make the move,” she says. “But don’t commit too soon. Keep yourself open.” She’s doing that now. “This move,” she adds, “is actually the most careful one I’ve ever made.”

P.S. The women in the picture on last October’s Fortune cover, above, are (l to r) Ning CEO Gina Bianchini, Singh Cassidy, Facebook COO Sheryl Sandberg, and Accel partner Theresia Gouw Ranzetta. Also, here are video excerpts of Singh Cassidy talking about power and about balancing family and career, from last September’s Fortune Most Powerful Women event in San Francisco.