You are misled by the phrase.
The phrase is not a complete sentence but a noun phrase.
The part "jikuu o koete haruka tabi suru" ([時空]{じくう}を[越]{こ}えて[遥]{はる}か[旅]{たび}する) modifies the noun "bokura" ([僕]{ぼく}ら). In Japanese, relative clauses modify a noun from before the target.
So the meaning of the phrase is like "we, who travel across time and space."
To mean what you said, you have to rearrange the phrase:
[僕]{ぼく}らは[時空]{じくう}を[越]{こ}えて[遥]{はる}か[旅]{たび}する。
bokura wa jikū o koete haruka tabisuru
By the way, you used the past tense "traveled" / "crossed" but it is not in past tense but present tense. To make it past tense you have to say "tabi shita"([旅]{たび}した).
In this case [旅]{たび}する can even mean "traveling" ([旅]{たび}をしている = tabi o shite iru).
UPDATE
From comment:
so koete is not the verb there, but an adverb? and tabisuru does work as a verb in the phrase, but how does haruka fits in there? haruka is an adjetive that means distant right? I thought "haruka tabisuru" translated as "distant journey" but if tabisuru is a verb it can't translate like that. Can you apply an adjetive to a verb in japanese?
Well, koeru ([越]{こ}える) is a verb and koete ([越]{こ}えて) is its te-form. te-form can be used like an adverb. Here, "jikuu o koete" ([時空]{じくう}を[越]{こ}えて) modifies the verb "tabi suru" ([旅]{たび}する = to travel). "jikuu o koeru" means "cross time and space" so "jikuu o koete" is "crossing time and space" or "across time and space."
"haruka," too, modifies the verb "tabi suru" ([旅]{たび}する). This word is not only an adjective but also an adverb. Here it is used as an adverb, meaning "far away" or "in the distance."
So "jikuu o koete haruka tabi suru" is "travel in the distance across time and space"