Veleba (feminine Velebová) is a Czech surname derived from the verb velebit (to praise). Notable people with the surname include:

Jan Veleba (athlete) (born 1986), Czech athlete Jan Veleba (politician), Czech politician Pavel Veleba, Czech footballer