One of the special charms of The Decemberists is that Colin Meloy, their chief songwriter, is a short-story writer at heart. (He, like your humble host, was at one time enrolled in the University of Montana's superlative creative-writing program.) "O Valencia," like most of their songs, tells a story -- a seemingly straightforward one about a Romeo-Juliet-style family feud ending tragically. (Pedro Flores created a video showing this story somewhat straightforwardly here.)
This dramatic remix of the story -- giving it a modern noirish twist, and featuring the band members as the lead actors -- is a product of Meloy's writerly bent (as well, evidently, of some cinematic ambitions). The extended version (more violent, but also clearer in terms of story) can be seen here.