Complex sentence: Despite their title they have long been a part of the Army and were renamed from their former colonial title in 1958.
Split into simpler sentences: Despite their title they have long been a part of the Army. They were renamed from their former colonial title in 1958.