Many Networks-on-Chip (NoC) applications exhibit one or more critical traffic flows that require hard Quality of Service (QoS). Guaranteeing bandwidth and latency for such real time flows is crucial. In this paper, we present novel methods to efficiently calculate worst-case bandwidth and latency bounds and thereby provide hard QoS guarantees. Importantly, the proposed methods apply even to best-effort NoC architectures,with no extra hardware dedicated to QoS support. By applying our methods to several realistic NoC designs, we show substantial improvements (on average, more than 30% in bandwidth and 50% in latency) in bound tightness with respect to existing approaches.