Abstract In the p-hub median problem we are given a set of clients V, a set of demands D ⊆ V × V , a cost function ρ : V × V → R + , and an integer p > 0 . The objective is to select terminals T ⊆ V , where | T | ≤ p , and assign each demand to a terminal, in order to minimize the total cost between demands and terminals. We present the first approximation bounds for the problem: a 1 + 2 / e lower bound if NP ⊂ DTIME ( n O ( log ⁡ log ⁡ n ) ) , and a (4α)-approximation algorithm if we are allowed to open at most ( 2 α 2 α − 1 ) p terminals, where α > 1 is a trade off parameter.