You are correct, you need to start from the kana.
I spent a few weeks learning hiragana from a book ("Let's learn Hiragana") and found it a very good reference material; plus it also gives you some basic vocab.
I've learned katakana through a different mean, though.
There is a game called "Slime Forest", which was created specifically to teach people kana. After playing it for about 8+ hours I memorized most of the katakana and filled some gaps in my hiragana knowledge. (I still used the book as reference material, though).
Basically, my advice is to use as many recourses as possible. Try to find a teacher online who will help you, or at least some penpals.
I have a teacher and he charges me a mere 50$ for 40 online lessons.
I'm also looking into a program called "Rosetta Stone", as I heard it's good when learning new languages.