In this paper, nineteen new binary linear codes are presented which improve the bounds on the maximum possible minimum distance. These codes belong to the class of quasi-cyclic (QC) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Six of the new codes meet the upper bound on minimum distance and so are optimal.